home *** CD-ROM | disk | FTP | other *** search
/ NOVA - For the NeXT Workstation / NOVA - For the NeXT Workstation.iso / Apps / ArchiveUtils / nx_arc / arclzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-20  |  22.7 KB  |  839 lines
  1. /*
  2.  * $Log:    arclzw.c,v $
  3.  * Revision 1.1  88/04/11  18:12:18  hyc
  4.  * Initial revision
  5.  * 
  6.  * Revision 1.2  87/12/20  03:17:39  hyc
  7.  * Fix some problems introduced by indent...
  8.  * 
  9.  * Revision 1.1  87/12/19  04:52:17  hyc
  10.  * Initial revision
  11.  * 
  12.  * Revision 1.3.1.1  87/08/13  17:03:36  hyc
  13.  * Run thru indent, fixed some signed vs. unsigned problems
  14.  * with bp <-> buf, and inbuf and localbuf...
  15.  *  Revision 1.3  87/07/21  11:41:41  hyc *** empty
  16.  * log message ***
  17.  * 
  18.  * Revision 1.2  87/07/21  08:45:24  hyc *** empty log message ***
  19.  * 
  20.  */
  21.  
  22. /*
  23.  * ARC - Archive utility - ARCLZW
  24.  * 
  25.  * Version 2.03, created on 10/24/86 at 11:46:22
  26.  * 
  27.  * (C) COPYRIGHT 1985,86 by System Enhancement Associates; ALL RIGHTS RESERVED
  28.  * 
  29.  * By:  Thom Henderson
  30.  * 
  31.  * Description: This file contains the routines used to implement Lempel-Zev
  32.  * data compression, which calls for building a coding table on the fly.
  33.  * This form of compression is especially good for encoding files which
  34.  * contain repeated strings, and can often give dramatic improvements over
  35.  * traditional Huffman SQueezing.
  36.  * 
  37.  * Language: Computer Innovations Optimizing C86
  38.  * 
  39.  * Programming notes: In this section I am drawing heavily on the COMPRESS
  40.  * program from UNIX.  The basic method is taken from "A Technique for High
  41.  * Performance Data Compression", Terry A. Welch, IEEE Computer Vol 17, No 6
  42.  * (June 1984), pp 8-19.  Also see "Knuth's Fundamental Algorithms", Donald
  43.  * Knuth, Vol 3, Section 6.4.
  44.  * 
  45.  * As best as I can tell, this method works by tracing down a hash table of code
  46.  * strings where each entry has the property:
  47.  * 
  48.  * if <string> <char> is in the table then <string> is in the table.
  49.  */
  50. #include <stdio.h>
  51. #include "arc.h"
  52.  
  53. /* definitions for older style crunching */
  54.  
  55. #define FALSE    0
  56. #define TRUE     !FALSE
  57. #define TABSIZE  4096
  58. #define NO_PRED  0xFFFF
  59. #define EMPTY    0xFFFF
  60. #define NOT_FND  0xFFFF
  61.  
  62. static unsigned INT inbuf;    /* partial input code storage */
  63. static INT      sp;        /* current stack pointer */
  64.  
  65. static struct entry {        /* string table entry format */
  66.     char            used;    /* true when this entry is in use */
  67.     unsigned INT    next;    /* ptr to next in collision list */
  68.     unsigned INT    predecessor;    /* code for preceeding string */
  69.     unsigned char   follower;    /* char following string */
  70. }               string_tab[TABSIZE];    /* the code string table */
  71.  
  72.  
  73. /* definitions for the new dynamic Lempel-Zev crunching */
  74.  
  75. #define BITS   12        /* maximum bits per code */
  76. #define HSIZE  5003        /* 80% occupancy */
  77. #define INIT_BITS 9        /* initial number of bits/code */
  78.  
  79. static INT      n_bits;        /* number of bits/code */
  80. static INT      maxcode;    /* maximum code, given n_bits */
  81. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  82. static INT      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  83.  
  84. static char     buf[BITS];    /* input/output buffer */
  85.  
  86. static unsigned char lmask[9] =    /* left side masks */
  87. {
  88.  0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00
  89. };
  90. static unsigned char rmask[9] =    /* right side masks */
  91. {
  92.  0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff
  93. };
  94.  
  95. static INT      offset;        /* byte offset for code output */
  96. static LONG     in_count;    /* length of input */
  97. static LONG     bytes_out;    /* length of compressed output */
  98. static LONG     bytes_ref;    /* output quality reference */
  99. static LONG     bytes_last;    /* output size at last checkpoint */
  100. static unsigned INT ent;
  101.  
  102. /*
  103.  * To save much memory (which we badly need at this point), we overlay the
  104.  * table used by the previous version of Lempel-Zev with those used by the
  105.  * new version.  Since no two of these routines will be used together, we can
  106.  * safely do this.
  107.  */
  108. #ifdef MSDOS
  109. static LONG    *htab = string_tab;    /* hash code table   (crunch) */
  110. #else
  111. static LONG     htab[HSIZE];
  112. #endif
  113. static unsigned INT codetab[HSIZE];    /* string code table (crunch) */
  114.  
  115. static unsigned INT *prefix = codetab;    /* prefix code table (uncrunch) */
  116. #ifdef MSDOS
  117. static unsigned char *suffix = string_tab;    /* suffix table (uncrunch) */
  118. #else
  119. static unsigned char suffix[HSIZE];
  120. #endif
  121.  
  122. static INT      free_ent;    /* first unused entry */
  123. static INT      firstcmp;    /* true at start of compression */
  124. static unsigned char stack[HSIZE];    /* local push/pop stack */
  125.  
  126. /*
  127.  * block compression parameters -- after all codes are used up, and
  128.  * compression rate changes, start over.
  129.  */
  130.  
  131. static INT      clear_flg;
  132. #define CHECK_GAP 2048        /* ratio check interval */
  133. static LONG     checkpoint;
  134. INT             upd_tab();
  135. static INT    putcode();
  136.  
  137. /*
  138.  * the next two codes should not be changed lightly, as they must not lie
  139.  * within the contiguous general code space.
  140.  */
  141. #define FIRST   257        /* first free entry */
  142. #define CLEAR   256        /* table clear output code */
  143.  
  144. /*
  145.  * The cl_block() routine is called at each checkpoint to determine if
  146.  * compression would likely improve by resetting the code table.  The method
  147.  * chosen to determine this is based on empirical observation that, in
  148.  * general, every 2k of input data should compress at least as well as the
  149.  * first 2k of input.
  150.  */
  151.  
  152. static          INT
  153. cl_block(t)            /* table clear for block compress */
  154.     FILE           *t;    /* our output file */
  155. {
  156.     checkpoint = in_count + CHECK_GAP;
  157.  
  158.     if (bytes_ref) {
  159.         if (bytes_out - bytes_last > bytes_ref) {
  160.             setmem(htab, HSIZE * sizeof(long), 0xff);
  161.             free_ent = FIRST;
  162.             clear_flg = 1;
  163.             putcode(CLEAR, t);
  164.             bytes_ref = 0;
  165.         }
  166.     } else
  167.         bytes_ref = bytes_out - bytes_last;
  168.  
  169.     bytes_last = bytes_out;    /* remember where we were */
  170. }
  171.  
  172. /*****************************************************************
  173.  *
  174.  * Output a given code.
  175.  * Inputs:
  176.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  177.  *              that n_bits =< (LONG)wordsize - 1.
  178.  * Outputs:
  179.  *      Outputs code to the file.
  180.  * Assumptions:
  181.  *      Chars are 8 bits long.
  182.  * Algorithm:
  183.  *      Maintain a BITS character long buffer (so that 8 codes will
  184.  * fit in it exactly).  When the buffer fills up empty it and start over.
  185.  */
  186.  
  187. static          INT
  188. putcode(code, t)        /* output a code */
  189.     INT             code;    /* code to output */
  190.     FILE           *t;    /* where to put it */
  191. {
  192.     INT             r_off = offset;    /* right offset */
  193.     INT             bits = n_bits;    /* bits to go */
  194.     char           *bp = buf;    /* buffer pointer */
  195.     INT             n;    /* index */
  196.  
  197.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  198.         bp += (r_off >> 3);
  199.         r_off &= 7;
  200.  
  201.         /*
  202.          * Since code is always >= 8 bits, only need to mask the
  203.          * first hunk on the left. 
  204.          */
  205.         *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  206.         bp++;
  207.         bits -= (8 - r_off);
  208.         code >>= (8 - r_off);
  209.  
  210.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  211.         if (bits >= 8) {
  212.             *bp++ = code;
  213.             code >>= 8;
  214.             bits -= 8;
  215.         }
  216.         /* Last bits. */
  217.         if (bits)
  218.             *bp = code;
  219.  
  220.         offset += n_bits;
  221.  
  222.         if (offset == (n_bits << 3)) {
  223.             bp = buf;
  224.             bits = n_bits;
  225.             bytes_out += bits;
  226.             do
  227.                 putc_pak(*bp++, t);
  228.             while (--bits);
  229.             offset = 0;
  230.         }
  231.         /*
  232.          * If the next entry is going to be too big for the code
  233.          * size, then increase it, if possible. 
  234.          */
  235.         if (free_ent > maxcode || clear_flg > 0) {
  236.             /*
  237.              * Write the whole buffer, because the input side
  238.              * won't discover the size increase until after
  239.              * it has read it. 
  240.              */
  241.             if (offset > 0) {
  242.                 bp = buf;    /* reset pointer for writing */
  243.                 bytes_out += n = n_bits;
  244.                 while (n--)
  245.                     putc_pak(*bp++, t);
  246.             }
  247.             offset = 0;
  248.  
  249.             if (clear_flg) {    /* reset if clearing */
  250.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  251.                 clear_flg = 0;
  252.             } else {/* else use more bits */
  253.                 n_bits++;
  254.                 if (n_bits == BITS)
  255.                     maxcode = maxcodemax;
  256.                 else
  257.                     maxcode = MAXCODE(n_bits);
  258.             }
  259.         }
  260.     } else {        /* dump the buffer on EOF */
  261.         bytes_out += n = (offset + 7) / 8;
  262.  
  263.         if (offset > 0)
  264.             while (n--)
  265.                 putc_pak(*bp++, t);
  266.         offset = 0;
  267.     }
  268. }
  269.  
  270. /*****************************************************************
  271.  *
  272.  * Read one code from the standard input.  If EOF, return -1.
  273.  * Inputs:
  274.  *      cmpin
  275.  * Outputs:
  276.  *      code or -1 is returned.
  277.  */
  278.  
  279. static          INT
  280. getcode(f)            /* get a code */
  281.     FILE           *f;    /* file to get from */
  282. {
  283.     INT             code;
  284.     static INT      offset = 0, size = 0;
  285.     INT             r_off, bits;
  286.     unsigned char  *bp = (unsigned char *) buf;
  287.  
  288.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  289.         /*
  290.          * If the next entry will be too big for the current code
  291.          * size, then we must increase the size. This implies
  292.          * reading a new buffer full, too. 
  293.          */
  294.         if (free_ent > maxcode) {
  295.             n_bits++;
  296.             if (n_bits == BITS)
  297.                 maxcode = maxcodemax;    /* won't get any bigger
  298.                              * now */
  299.             else
  300.                 maxcode = MAXCODE(n_bits);
  301.         }
  302.         if (clear_flg > 0) {
  303.             maxcode = MAXCODE(n_bits = INIT_BITS);
  304.             clear_flg = 0;
  305.         }
  306.         for (size = 0; size < n_bits; size++) {
  307.             if ((code = getc_unp(f)) == EOF)
  308.                 break;
  309.             else
  310.                 buf[size] = code;
  311.         }
  312.         if (size <= 0)
  313.             return -1;    /* end of file */
  314.  
  315.         offset = 0;
  316.         /* Round size down to integral number of codes */
  317.         size = (size << 3) - (n_bits - 1);
  318.     }
  319.     r_off = offset;
  320.     bits = n_bits;
  321.  
  322.     /*
  323.      * Get to the first byte. 
  324.      */
  325.     bp += (r_off >> 3);
  326.     r_off &= 7;
  327.  
  328.     /* Get first part (low order bits) */
  329.     code = (*bp++ >> r_off);
  330.     bits -= 8 - r_off;
  331.     r_off = 8 - r_off;    /* now, offset into code word */
  332.  
  333.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  334.     if (bits >= 8) {
  335.         code |= *bp++ << r_off;
  336.         r_off += 8;
  337.         bits -= 8;
  338.     }
  339.     /* high order bits. */
  340.     code |= (*bp & rmask[bits]) << r_off;
  341.     offset += n_bits;
  342.  
  343.     return code & MAXCODE(BITS);
  344. }
  345.  
  346. /*
  347.  * compress a file
  348.  * 
  349.  * Algorithm:  use open addressing double hashing (no chaining) on the prefix
  350.  * code / next character combination.  We do a variant of Knuth's algorithm D
  351.  * (vol. 3, sec. 6.4) along with G. Knott's relatively-prime secondary probe.
  352.  * Here, the modular division first probe is gives way to a faster
  353.  * exclusive-or manipulation.  Also do block compression with an adaptive
  354.  * reset, where the code table is cleared when the compression ratio
  355.  * decreases, but after the table fills.  The variable-length output codes
  356.  * are re-sized at this point, and a special CLEAR code is generated for the
  357.  * decompressor.
  358.  */
  359.  
  360. INT
  361. init_cm(f, t)            /* initialize for compression */
  362.     FILE           *f;    /* file we will be compressing */
  363.     FILE           *t;    /* where we will put it */
  364. {
  365.     offset = 0;
  366.     bytes_out = bytes_last = 1;
  367.     bytes_ref = 0;
  368.     clear_flg = 0;
  369.     in_count = 1;
  370.     checkpoint = CHECK_GAP;
  371.     maxcode = MAXCODE(n_bits = INIT_BITS);
  372.     free_ent = FIRST;
  373.     setmem(htab, HSIZE * sizeof(LONG), 0xff);
  374.     n_bits = INIT_BITS;    /* set starting code size */
  375.  
  376.     putc_pak(BITS, t);    /* note our max code length */
  377.  
  378.     firstcmp = 1;        /* next byte will be first */
  379. }
  380.  
  381. INT
  382. putc_cm(c, t)            /* compress a character */
  383.     unsigned char   c;    /* character to compress */
  384.     FILE           *t;    /* where to put it */
  385. {
  386.     static LONG     fcode;
  387.     static INT      hshift;
  388.     INT             i;
  389.     INT             disp;
  390.  
  391.     if (firstcmp) {        /* special case for first byte */
  392.         ent = c;    /* remember first byte */
  393.  
  394.         hshift = 0;
  395.         for (fcode = (LONG) HSIZE; fcode < 65536L; fcode *= 2L)
  396.             hshift++;
  397.         hshift = 8 - hshift;    /* set hash code range bound */
  398.  
  399.         firstcmp = 0;    /* no longer first */
  400.         return;
  401.     }
  402.     in_count++;
  403.  
  404.     fcode = (LONG) (((LONG) c << BITS) + ent);
  405.     i = (c << hshift) ^ ent;/* xor hashing */
  406.  
  407.     if (htab[i] == fcode) {
  408.         ent = codetab[i];
  409.         return;
  410.     } else if (htab[i] < 0)    /* empty slot */
  411.         goto nomatch;
  412.     disp = HSIZE - i;    /* secondary hash (after G.Knott) */
  413.     if (i == 0)
  414.         disp = 1;
  415.  
  416. probe:
  417.     if ((i -= disp) < 0)
  418.         i += HSIZE;
  419.  
  420.     if (htab[i] == fcode) {
  421.         ent = codetab[i];
  422.         return;
  423.     }
  424.     if (htab[i] > 0)
  425.         goto probe;
  426.  
  427. nomatch:
  428.     putcode(ent, t);
  429.     ent = c;
  430.     if (free_ent < maxcodemax) {
  431.         codetab[i] = free_ent++;    /* code -> hashtable */
  432.         htab[i] = fcode;
  433.     }
  434.     if (in_count >= checkpoint)
  435.         cl_block(t);    /* check for adaptive reset */
  436. }
  437.  
  438. LONG
  439. pred_cm(t)            /* finish compressing a file */
  440.     FILE           *t;    /* where to put it */
  441. {
  442.     putcode(ent, t);    /* put out the final code */
  443.     putcode(-1, t);        /* tell output we are done */
  444.  
  445.     return bytes_out;    /* say how big it got */
  446. }
  447.  
  448. /*
  449.  * Decompress a file.  This routine adapts to the codes in the file building
  450.  * the string table on-the-fly; requiring no table to be stored in the
  451.  * compressed file.  The tables used herein are shared with those of the
  452.  * compress() routine.  See the definitions above.
  453.  */
  454.  
  455. INT
  456. decomp(f, t)            /* decompress a file */
  457.     FILE           *f;    /* file to read codes from */
  458.     FILE           *t;    /* file to write text to */
  459. {
  460.     unsigned char  *stackp;
  461.     INT             finchar;
  462.     INT             code, oldcode, incode;
  463.  
  464.     if ((code = getc_unp(f)) != BITS)
  465.         arc_abort("File packed with %d bits, I can only handle %d", code, BITS);
  466.  
  467.     n_bits = INIT_BITS;    /* set starting code size */
  468.     clear_flg = 0;
  469.  
  470.     /*
  471.      * As above, initialize the first 256 entries in the table. 
  472.      */
  473.     maxcode = MAXCODE(n_bits = INIT_BITS);
  474.     setmem(prefix, 256 * sizeof(INT), 0);    /* reset decode string table */
  475.     for (code = 255; code >= 0; code--)
  476.         suffix[code] = (unsigned char) code;
  477.  
  478.     free_ent = FIRST;
  479.  
  480.     finchar = oldcode = getcode(f);
  481.     if (oldcode == -1)    /* EOF already? */
  482.         return;        /* Get out of here */
  483.     putc_ncr((char) finchar, t);    /* first code must be 8 bits=char */
  484.     stackp = stack;
  485.  
  486.     while ((code = getcode(f)) > -1) {
  487.         if (code == CLEAR) {    /* reset string table */
  488.             setmem(prefix, 256 * sizeof(INT), 0);
  489.             clear_flg = 1;
  490.             free_ent = FIRST - 1;
  491.             if ((code = getcode(f)) == -1)    /* O, untimely death! */
  492.                 break;
  493.         }
  494.         incode = code;
  495.         /*
  496.          * Special case for KwKwK string. 
  497.          */
  498.         if (code >= free_ent) {
  499.             *stackp++ = finchar;
  500.             code = oldcode;
  501.         }
  502.         /*
  503.          * Generate output characters in reverse order 
  504.          */
  505.         while (code >= 256) {
  506.             *stackp++ = suffix[code];
  507.             code = prefix[code];
  508.         }
  509.         *stackp++ = finchar = suffix[code];
  510.  
  511.         /*
  512.          * And put them out in forward order 
  513.          */
  514.         do
  515.             putc_ncr(*--stackp, t);
  516.         while (stackp > stack);
  517.  
  518.         /*
  519.          * Generate the new entry. 
  520.          */
  521.         if ((code = free_ent) < maxcodemax) {
  522.             prefix[code] = (unsigned short) oldcode;
  523.             suffix[code] = finchar;
  524.             free_ent = code + 1;
  525.         }
  526.         /*
  527.          * Remember previous code. 
  528.          */
  529.         oldcode = incode;
  530.     }
  531. }
  532.  
  533.  
  534. /*************************************************************************
  535.  * Please note how much trouble it can be to maintain upwards            *
  536.  * compatibility.  All that follows is for the sole purpose of unpacking *
  537.  * files which were packed using an older method.                        *
  538.  *************************************************************************/
  539.  
  540.  
  541. /*
  542.  * The h() pointer points to the routine to use for calculating a hash value.
  543.  * It is set in the init routines to point to either of oldh() or newh().
  544.  * 
  545.  * oldh() calculates a hash value by taking the middle twelve bits of the square
  546.  * of the key.
  547.  * 
  548.  * newh() works somewhat differently, and was tried because it makes ARC about
  549.  * 23% faster.  This approach was abandoned because dynamic Lempel-Zev
  550.  * (above) works as well, and packs smaller also.  However, inadvertent
  551.  * release of a developmental copy forces us to leave this in.
  552.  */
  553.  
  554. static unsigned INT(*h) ();    /* pointer to hash function */
  555.  
  556. static unsigned INT
  557. oldh(pred, foll)        /* old hash function */
  558.     unsigned INT    pred;    /* code for preceeding string */
  559.     unsigned char   foll;    /* value of following char */
  560. {
  561.     LONG            local;    /* local hash value */
  562.  
  563.     local = ((pred + foll) | 0x0800) & 0xFFFF; /* create the hash key */
  564.     local *= local;        /* square it */
  565.     return (local >> 6) & 0x0FFF;    /* return the middle 12 bits */
  566. }
  567.  
  568. static unsigned INT
  569. newh(pred, foll)        /* new hash function */
  570.     unsigned INT    pred;    /* code for preceeding string */
  571.     unsigned char   foll;    /* value of following char */
  572. {
  573.     return (((pred + foll) & 0xFFFF) * 15073) & 0xFFF; /* faster hash */
  574. }
  575.  
  576. /*
  577.  * The eolist() function is used to trace down a list of entries with
  578.  * duplicate keys until the last duplicate is found.
  579.  */
  580.  
  581. static unsigned INT
  582. eolist(index)            /* find last duplicate */
  583.     unsigned INT    index;
  584. {
  585.     INT             temp;
  586.  
  587.     while (temp = string_tab[index].next)    /* while more duplicates */
  588.         index = temp;
  589.  
  590.     return index;
  591. }
  592.  
  593. /*
  594.  * The hash() routine is used to find a spot in the hash table for a new
  595.  * entry.  It performs a "hash and linear probe" lookup, using h() to
  596.  * calculate the starting hash value and eolist() to perform the linear
  597.  * probe.  This routine DOES NOT detect a table full condition.  That MUST be
  598.  * checked for elsewhere.
  599.  */
  600.  
  601. static unsigned INT
  602. hash(pred, foll)        /* find spot in the string table */
  603.     unsigned INT    pred;    /* code for preceeding string */
  604.     unsigned char   foll;    /* char following string */
  605. {
  606.     unsigned INT    local, tempnext;    /* scratch storage */
  607.     struct entry   *ep;    /* allows faster table handling */
  608.  
  609.     local = (*h) (pred, foll);    /* get initial hash value */
  610.  
  611.     if (!string_tab[local].used)    /* if that spot is free */
  612.         return local;    /* then that's all we need */
  613.  
  614.     else {            /* else a collision has occured */
  615.         local = eolist(local);    /* move to last duplicate */
  616.  
  617.         /*
  618.          * We must find an empty spot. We start looking 101 places
  619.          * down the table from the last duplicate. 
  620.          */
  621.  
  622.         tempnext = (local + 101) & 0x0FFF;
  623.         ep = &string_tab[tempnext];    /* initialize pointer */
  624.  
  625.         while (ep->used) {    /* while empty spot not found */
  626.             if (++tempnext == TABSIZE) {    /* if we are at the end */
  627.                 tempnext = 0;    /* wrap to beginning of table */
  628.                 ep = string_tab;
  629.             } else
  630.                 ++ep;    /* point to next element in table */
  631.         }
  632.  
  633.         /*
  634.          * local still has the pointer to the last duplicate, while
  635.          * tempnext has the pointer to the spot we found.  We use
  636.          * this to maintain the chain of pointers to duplicates. 
  637.          */
  638.  
  639.         string_tab[local].next = tempnext;
  640.  
  641.         return tempnext;
  642.     }
  643. }
  644.  
  645. /*
  646.  * The unhash() function is used to search the hash table for a given key.
  647.  * Like hash(), it performs a hash and linear probe search.  It returns
  648.  * either the number of the entry (if found) or NOT_FND (if not found).
  649.  */
  650.  
  651. static unsigned INT
  652. unhash(pred, foll)        /* search string table for a key */
  653.     unsigned INT    pred;    /* code of preceeding string */
  654.     unsigned char   foll;    /* character following string */
  655. {
  656.     unsigned INT    local, offset;    /* scratch storage */
  657.     struct entry   *ep;    /* this speeds up access */
  658.  
  659.     local = (*h) (pred, foll);    /* initial hash */
  660.  
  661.     while (1) {
  662.         ep = &string_tab[local];    /* speed up table access */
  663.  
  664.         if ((ep->predecessor == pred) && (ep->follower == foll))
  665.             return local;    /* we have a match */
  666.  
  667.         if (!ep->next)    /* if no more duplicates */
  668.             return NOT_FND;    /* then key is not listed */
  669.  
  670.         local = ep->next;    /* move on to next duplicate */
  671.     }
  672. }
  673.  
  674. /*
  675.  * The init_tab() routine is used to initialize our hash table. You realize,
  676.  * of course, that "initialize" is a complete misnomer.
  677.  */
  678.  
  679. static          INT
  680. init_tab()
  681. {                /* set ground state in hash table */
  682.     unsigned INT    i;    /* table index */
  683.  
  684.     setmem((char *) string_tab, sizeof(string_tab), 0);
  685.  
  686.     for (i = 0; i < 256; i++)    /* list all single byte strings */
  687.         upd_tab(NO_PRED, i);
  688.  
  689.     inbuf = EMPTY;        /* nothing is in our buffer */
  690. }
  691.  
  692. /*
  693.  * The upd_tab routine is used to add a new entry to the string table. As
  694.  * previously stated, no checks are made to ensure that the table has any
  695.  * room.  This must be done elsewhere.
  696.  */
  697.  
  698. INT
  699. upd_tab(pred, foll)        /* add an entry to the table */
  700.     unsigned INT    pred;    /* code for preceeding string */
  701.     unsigned INT    foll;    /* character which follows string */
  702. {
  703.     struct entry   *ep;    /* pointer to current entry */
  704.  
  705.     /* calculate offset just once */
  706.  
  707.     ep = &string_tab[hash(pred, foll)];
  708.  
  709.     ep->used = TRUE;    /* this spot is now in use */
  710.     ep->next = 0;        /* no duplicates after this yet */
  711.     ep->predecessor = pred;    /* note code of preceeding string */
  712.     ep->follower = foll;    /* note char after string */
  713. }
  714.  
  715. /*
  716.  * This algorithm encoded a file into twelve bit strings (three nybbles). The
  717.  * gocode() routine is used to read these strings a byte (or two) at a time.
  718.  */
  719.  
  720. static          INT
  721. gocode(fd)            /* read in a twelve bit code */
  722.     FILE           *fd;    /* file to get code from */
  723. {
  724.     unsigned INT    localbuf, returnval;
  725.     INT             temp;
  726.  
  727.     if (inbuf == EMPTY) {    /* if on a code boundary */
  728.         if ((temp = getc_unp(fd)) == EOF)    /* get start of next
  729.                              * code */
  730.             return EOF;    /* pass back end of file status */
  731.         localbuf = temp & 0xFF;    /* mask down to true byte value */
  732.         if ((temp = getc_unp(fd)) == EOF)
  733.             /* get end of code, * start of next */
  734.             return EOF;    /* this should never happen */
  735.         inbuf = temp & 0xFF;    /* mask down to true byte value */
  736.  
  737.         returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
  738.         inbuf &= 0x000F;/* leave partial code pending */
  739.     } else {        /* buffer contains first nybble */
  740.         if ((temp = getc_unp(fd)) == EOF)
  741.             return EOF;
  742.         localbuf = temp & 0xFF;
  743.  
  744.         returnval = localbuf + ((inbuf << 8) & 0xF00);
  745.         inbuf = EMPTY;    /* note no hanging nybbles */
  746.     }
  747.     return returnval;    /* pass back assembled code */
  748. }
  749.  
  750. static          INT
  751. push(c)                /* push char onto stack */
  752.     INT             c;    /* character to push */
  753. {
  754.     stack[sp] = ((char) c);    /* coerce integer into a char */
  755.  
  756.     if (++sp >= TABSIZE)
  757.         arc_abort("Stack overflow\n");
  758. }
  759.  
  760. static          INT
  761. pop()
  762. {                /* pop character from stack */
  763.     if (sp > 0)
  764.         return ((int) stack[--sp]);    /* leave ptr at next empty
  765.                          * slot */
  766.  
  767.     else
  768.         return EMPTY;
  769. }
  770.  
  771. /***** LEMPEL-ZEV DECOMPRESSION *****/
  772.  
  773. static INT      code_count;    /* needed to detect table full */
  774. static unsigned INT code;    /* where we are so far */
  775. static INT      firstc;        /* true only on first character */
  776.  
  777. INT
  778. init_ucr(new)            /* get set for uncrunching */
  779.     INT             new;    /* true to use new hash function */
  780. {
  781.     if (new)        /* set proper hash function */
  782.         h = newh;
  783.     else
  784.         h = oldh;
  785.  
  786.     sp = 0;            /* clear out the stack */
  787.     init_tab();        /* set up atomic code definitions */
  788.     code_count = TABSIZE - 256;    /* note space left in table */
  789.     firstc = 1;        /* true only on first code */
  790. }
  791.  
  792. INT
  793. getc_ucr(f)            /* get next uncrunched byte */
  794.     FILE           *f;    /* file containing crunched data */
  795. {
  796.     unsigned INT    c;    /* a character of input */
  797.     INT             code, newcode;
  798.     static INT      oldcode, finchar;
  799.     struct entry   *ep;    /* allows faster table handling */
  800.  
  801.     if (firstc) {        /* first code is always known */
  802.         firstc = FALSE;    /* but next will not be first */
  803.         oldcode = gocode(f);
  804.         return finchar = string_tab[oldcode].follower;
  805.     }
  806.     if (!sp) {        /* if stack is empty */
  807.         if ((code = newcode = gocode(f)) == EOF)
  808.             return EOF;
  809.  
  810.         ep = &string_tab[code];    /* initialize pointer */
  811.  
  812.         if (!ep->used) {/* if code isn't known */
  813.             code = oldcode;
  814.             ep = &string_tab[code];    /* re-initialize pointer */
  815.             push(finchar);
  816.         }
  817.         while (ep->predecessor != NO_PRED) {
  818.             push(ep->follower);    /* decode string backwards */
  819.             code = ep->predecessor;
  820.             ep = &string_tab[code];
  821.         }
  822.  
  823.         push(finchar = ep->follower);    /* save first character also */
  824.  
  825.         /*
  826.          * The above loop will terminate, one way or another, with
  827.          * string_tab[code].follower equal to the first character in
  828.          * the string. 
  829.          */
  830.  
  831.         if (code_count) {    /* if room left in string table */
  832.             upd_tab(oldcode, finchar);
  833.             --code_count;
  834.         }
  835.         oldcode = newcode;
  836.     }
  837.     return pop();        /* return saved character */
  838. }
  839.